package org.example;

import java.util.Arrays;

public class HeapChangeUpAndDown {
    public static void main(String[] args) {
        int[] elem = {1,2,4,32,6,7,22,2,30,39,20};
        heapSort(elem);
        System.out.println("Sorted: " + Arrays.toString(elem));
    }

    // 堆排序主函数
    private static void heapSort(int[] arr) {
        //构建小根堆
        for (int i = arr.length/2 - 1; i >= 0; i--) {
            shiftDown(arr, i, arr.length); // 修正1：传入堆的当前大小
        }

        // 2. 依次取出堆顶元素（交换后调整）
        for (int end = arr.length-1; end > 0; end--) {
            swap(arr, 0, end);
            shiftDown(arr, 0, end); // 修正2：传入当前堆的有效长度（end）
        }
    }

    // 堆调整（最大堆）
    private static void shiftDown(int[] arr, int parent, int size) { // 修正3：添加size参数
        int child = parent*2 + 1;
        while (child < size) {
            // 选择较大的子节点
            if (child + 1 < size && arr[child] < arr[child+1]) {
                child++;
            }
            // 若父节点 >= 子节点，无需调整
            if (arr[parent] >= arr[child]) { // 修正4：修复条件判断逻辑
                break;
            }
            swap(arr, parent, child);
            parent = child;
            child = parent*2 + 1;
        }
    }
    public void shiftUp(int child) {
    // 找到child的双亲
            int parent = (child - 1) / 2;
            int[] array = {12};
            while (child > 0) {
    // 如果双亲⽐孩⼦⼤，parent满⾜堆的性质，调整结束
                if (array[parent] > array[child]) {
                    break;
                }
                else{
// 将双亲与孩⼦节点进⾏交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
// ⼩的元素向下移动，可能到值⼦树不满⾜对的性质，因此需要继续向上调增
                child = parent;
                parent = (child - 1) / 1;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}